//Eric Leschinski..
//boggle game
//implementation

#pragma hdrstop


#include"stack.h"

#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<ctype.h>

using namespace std;

unjumbleclass::unjumbleclass()
{
   path = new stack<char>(1000);
}
//=====================================================================
int unjumbleclass::visit(int place, int camefrom)
{
   letterstaken[place] = true;   //we cant use this letter again.
   path->push(theword[place]);      //arrive at a spot, put it on the stack.
   int result = binarysearch();    //see if this is a good word or not.

   if (result == 1)
   {
          //cout<<path->getstringstack()<<"  ";  //used to show we found a word
          strcpy(answerarray[answercounter], path->getstringstack());
          answercounter++;                                 //was a match
   }
   else if (result == 0)
   {
   }
   else if (result == -1)
   {
      return 0;
   }
   for (int i = 0; i < sizeword; i++)
   {
      if (letterstaken[i] == false)
      {
         visit(i, 0);
         letterstaken[i] = false;
         path->pop();
      }
   }
   return 0;
}

//=====================================================================
char *unjumbleclass::trunkateword(char *word, int amt)
{
   char *passback = new char[amt+1];

   strncpy(passback, word, amt);
   passback[amt] = '\0';
   //cout<<"passback from trunkateword is: "<<passback<<endl;
   return passback;
}
//=====================================================================
int unjumbleclass::binarysearch()
{
char *word = new char[path->count() + 1];     //'word' may hold a whole valid word,
                                              //or just a part of a word, it will be
                                              //checked against the english via
                                              //binary search.  path->count makes the
                                              //size of the array exactly as large as
                                              //it needs to be.
//cout<<"the size of the stack is: "<<(path->count())<<endl;

bool keepgoing = false;
int trunkateletters = path->count();    //when we are looking for a word such as
                                        // 'supp' we will not find this in the
                                        //englishwords, we need to trunkate the
                                        //english words, so we will continue looking
                                        //for words such as 'supply'.  however
                                        //we do not want to waste energy looking
                                        //for words that start with 'zxpim" because
                                        //there are none.  trunkate handles this.

word = path->getstringstack();     //from our stack of characters,
                                   //getstringstack assembles the chars
                                   //and puts it into a string.

//cout<<"test: "<<word<<endl;

int lowindex = 0, highindex = sizeofenglish, endsearch, testnumber;
                      //lowindex and highindex is how the computer skipps most
                      //of the 40,000 items, the computer looks half way from
                      //top to bottom and checks if the word that it wants is up or down,
                      //if up, then it cuts that in half, and checks the middle.



//cout<<"sizeofenglish is: "<<sizeofenglish<<endl;
//testnumber = lowindex + ((highindex - lowindex)/2);
                       //test number is the spot in the 'englishwords' array that
                       //it is currently checking, this equation cuts the run in
                       //half, cutting the workload by a million fold.


while (true){

     testnumber = lowindex + ((highindex - lowindex)/2);
     endsearch = highindex + lowindex;
     //cout<<"our test number is: "<<testnumber<<", and our word is: "<<english[testnumber].chrword<<endl;
                         //strcmp takes char * only, when the left is smaller than
                         //the right, the return is less than zero.




//cout<<"compare this: "<<trunkateword(english[testnumber].chrword, trunkateletters)<<"."<<endl;
//cout<<"to this: "<<word<<"."<<endl;

if (strcmp(trunkateword(english[testnumber].chrword, trunkateletters), word) == 0)
     keepgoing = true;

if (strcmp(word, english[testnumber].chrword) == 0){

               //cout<<word<<" WAS found a perfect match"<<endl;
               return 1;

     }
     else if (strcmp(english[testnumber].chrword, word) > 0){
          highindex = testnumber;//(highindex - (highindex - lowindex) / 2);
          //cout<<" We had to shuffle down"<<endl;
     }
     else if (strcmp(english[testnumber].chrword, word) < 0){
          lowindex = testnumber; //lowindex + ((highindex - lowindex) / 2);
          //cout<<"   We had to shuffle up"<<endl;
     }
     else{
          cout<<"you thucked up numba six"<<endl;
     }
     if (endsearch == (highindex + lowindex)){
          if (keepgoing)
               return 0;
          //cout<<"   Endsearch has been reached, no words start with this, nor any matches"<<endl;
          return -1;
               //if highindex or lowindex didnt change then the letters are not here
     }
}
//the computer should never get this far:
cout<<"if you read this in ur prog, you thucked up numba six!"<<endl;
}

//============================================
char **unjumbleclass::getanswers(char **&answers)
{
   for(int x = 0; x < answercounter; x++)
   {
      strcpy(answers[x], answerarray[x]);
   }
}
//==================================================================
int unjumbleclass::getnumanswers()
{
   return answercounter;
}
//==============================================================
void unjumbleclass::sortanswerwords()
{
   char **temparray;
   int smallest;
   int sz, location;

   temparray = new char *[100000];
   for(int x = 0; x < 100000; x++)
   {
      temparray[x] = new char[30];
   }

   for(int x = 0; x < answercounter; x++)
   {
      smallest = 100;
      for(int y = 0; y < answercounter; y++)
      {
         sz = SizeWord2(answerarray[y]);
         if ((sz != 0) && (sz < smallest))
         {
            smallest = sz;
            location = y;
         }
      }
      strcpy(temparray[x], answerarray[location]);
      strcpy(answerarray[location], "");
   }
   for(int x = 0; x < answercounter; x++)
   {
      strcpy(answerarray[x], temparray[x]);
   }
}
//==================================================================
void unjumbleclass::ClearTaken()
{
   for(int x = 0; x < sizeword; x++)
   {
      letterstaken[x] = false;
   }
}
//==================================================================
int unjumbleclass::SizeWord2(char *word)
{
   string n;
   n = word;
   return n.length();
}
//==================================================================
void unjumbleclass::UnJumbleWord(char *w, int &err)
{
   theword = new char[30];
   strcpy(theword, w);

   answerarray = new char*[100000];   //holds the answer words
   for (int a = 0; a < 100000; a++)          //make the answer array
      answerarray[a] = new char[30];

   char n[40];
   ifstream data;

   data.open("englishrevise.txt", ios::in);
   if (!data)
      data.open("wordsfile.txt", ios::in);
   if (!data)
      data.open("wordsfile.txt.txt", ios::in);
   if (!data)
      data.open("wordsfile", ios::in);
   if (!data)
   {
      err = 1;
      return;
   }
   int z = 0;
   while (!data.eof()){
      data>>n;
      z++;
   }
   sizeofenglish = z;
   answercounter = 0;

   english = new listwords[sizeofenglish+2];

   cout<<"There are: "<<z<<" things in this text file."<<endl;

   data.close();

   data.open("englishrevise.txt", ios::in);
   if (!data)
      data.open("wordsfile.txt", ios::in);
   if (!data)
      data.open("wordsfile.txt.txt", ios::in);
   if (!data)
      data.open("wordsfile", ios::in);
   int x = 0;

   while (!data.eof()){
      data >> english[x].chrword;
      x++;
   }

   sizeword = SizeWord2(w);
   letterstaken = new bool[sizeword+1];

   for(int x = 0; x < sizeword; x++)
   {
      ClearTaken();
      path->empty();
      //letterstaken[x] = true;
      visit(x, -1);  //came from is -1 which means we appeared.
      path->pop();
   }
   err = 0;
   return;
}
